{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort Features by Popularity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortFeatures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #按受欢迎程度排列功能"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串数组 <code>features</code> ，其中 <code>features[i]</code> 是一个单词，描述你最近参与开发的项目中一个功能的名称。你调查了用户喜欢哪些功能。另给定一个字符串数组 <code>responses</code>，其中 <code>responses[i]</code> 是一个包含以空格分隔的一系列单词的字符串。</p>\n",
    "\n",
    "<p>你想要按照受欢迎程度排列这些功能。 严格地说，令 <code>appearances(word)</code> 是满足 <code>responses[i]</code> 中包含单词 <code>word</code> 的 <code>i</code> 的个数，则当 <code>appearances(features[x]) > appearances(features[y])</code> 时，第 <code>x</code> 个功能比第 <code>y</code> 个功能更受欢迎。</p>\n",
    "\n",
    "<p>返回一个数组 <code>sortedFeatures</code> ，包含按受欢迎程度排列的功能名称。当第 <code>x</code>  个功能和第 <code>y</code> 个功能的受欢迎程度相同且 <code>x < y</code> 时，你应当将第 <code>x</code> 个功能放在第 <code>y</code> 个功能之前。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入</strong><b>：</b>features = [\"cooler\",\"lock\",\"touch\"], responses = [\"i like cooler cooler\",\"lock touch cool\",\"locker like touch\"]\n",
    "<strong>输出</strong><b>：</b>[\"touch\",\"cooler\",\"lock\"]\n",
    "<strong>解释</strong><b>：</b>appearances(\"cooler\") = 1，appearances(\"lock\") = 1，appearances(\"touch\") = 2。由于 \"cooler\" 和 \"lock\" 都出现了 1 次，且 \"cooler\" 在原数组的前面，所以 \"cooler\" 也应该在结果数组的前面。\n",
    "</pre>\n",
    "\n",
    "<p><b>示例 2：</b></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入</strong><b>：</b>features = [\"a\",\"aa\",\"b\",\"c\"], responses = [\"a\",\"a aa\",\"a a a a a\",\"b a\"]\n",
    "<strong>输出</strong><b>：</b>[\"a\",\"aa\",\"b\",\"c\"]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= features.length <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= features[i].length <= 10</code></li>\n",
    "\t<li><code>features</code> 不包含重复项。</li>\n",
    "\t<li><code>features[i]</code> 由小写字母构成。</li>\n",
    "\t<li><code>1 <= responses.length <= 10<sup>2</sup></code></li>\n",
    "\t<li><code>1 <= responses[i].length <= 10<sup>3</sup></code></li>\n",
    "\t<li><code>responses[i]</code> 由小写字母和空格组成。</li>\n",
    "\t<li><code>responses[i]</code> 不包含两个连续的空格。</li>\n",
    "\t<li><code>responses[i]</code> 没有前置或后置空格。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-features-by-popularity](https://leetcode.cn/problems/sort-features-by-popularity/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-features-by-popularity](https://leetcode.cn/problems/sort-features-by-popularity/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"cooler\",\"lock\",\"touch\"]\\n[\"i like cooler cooler\",\"lock touch cool\",\"locker like touch\"]', '[\"a\",\"aa\",\"b\",\"c\"]\\n[\"a\",\"a aa\",\"a a a a a\",\"b a\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortFeatures(self, features: List[str], responses: List[str]) -> List[str]:\n",
    "        hashmap = defaultdict(int)\n",
    "        for resp in responses:\n",
    "            for w in set(resp.split()):\n",
    "                hashmap[w]+=1\n",
    "        features.sort(key=lambda a:-hashmap[a])\n",
    "        return features\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def sortFeatures(self, features: List[str], responses: List[str]) -> List[str]:\n",
    "        # 创建一个 Counter 对象来存储每个功能出现的次数。\n",
    "        feature_count = Counter()\n",
    "        \n",
    "        # 计算每个功能在所有回应中出现的次数。\n",
    "        for response in responses:\n",
    "            # 使用 set 来存储每个回应中出现的唯一功能。\n",
    "            unique_features = set(response.split())\n",
    "            for feature in unique_features:\n",
    "                if feature in features:\n",
    "                    feature_count[feature] += 1\n",
    "        \n",
    "        # 对功能进行排序。\n",
    "        # 使用 lambda 函数，以 feature_count 中的出现次数为主要排序键，\n",
    "        # 以 features 中的索引为次要排序键。\n",
    "        sorted_features = sorted(features, key=lambda x: (-feature_count[x], features.index(x)))\n",
    "        \n",
    "        return sorted_features\n",
    "\n",
    "# 测试代码\n",
    "features = [\"vote\", \"comment\", \"share\"]\n",
    "responses = [\"i love to vote\", \"comment is good\", \"share is awesome\", \"i like to comment\", \"vote vote vote\"]\n",
    "s = Solution()\n",
    "print(s.sortFeatures(features, responses))  # 输出应该是 ['vote', 'comment', 'share']\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortFeatures(self, features: List[str], responses: List[str]) -> List[str]:\n",
    "        cnts = Counter()\n",
    "        for x in responses:\n",
    "            for y in set(x.split()):\n",
    "                cnts[y] += 1\n",
    "        # print(cnts)\n",
    "        dct = {x:i for i, x in enumerate(features)}\n",
    "        return sorted(features, key=lambda x: (-cnts[x], dct[x]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortFeatures(self, features: List[str], responses: List[str]) -> List[str]:\n",
    "        counter = defaultdict(int)\n",
    "        index = {w: i for i, w in enumerate(features)}\n",
    "        for rsp in responses:\n",
    "            words = set(rsp.split(\" \"))\n",
    "            for it in words:\n",
    "                counter[it] += 1\n",
    "        features.sort(key=lambda x: (-counter.get(x, 0), index[x]))\n",
    "        return features\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 排序\n",
    "    # 定制化排序函数即可，需要提前建立两个map，一个map用来保存feature 到其index的映射，以便频率相同时，按照下标升序排列。另外一个map，保存feature到其出现频率的映射。注意这里需要用set将同一个调查反馈中的feature唯一化一下，因为同一个调查问卷中出现一个feature多次只能算一次，用set再合适不过。具体实现C++/Java/Python都差不多，仅仅是语法的区别。大家根据偏好，从下面的tab里选择自己喜欢的版本看就好。\n",
    "    def sortFeatures(self, features: List[str], responses: List[str]) -> List[str]:\n",
    "        featureSet = set(features)\n",
    "        order = {word : i for i, word in enumerate(features)}\n",
    "        freq = collections.defaultdict(int)\n",
    "        for r in responses:\n",
    "            for word in set(r.split(' ')):\n",
    "                if word in featureSet:\n",
    "                    freq[word] += 1\n",
    "\n",
    "        features.sort(key = lambda x : (-freq[x], order[x]))\n",
    "\n",
    "        return features\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
